/* This file is derived from source code for the Nachos
   instructional operating system.  The Nachos copyright notice
   is reproduced in full below. */

/* Copyright (c) 1992-1996 The Regents of the University of California.
   All rights reserved.

   Permission to use, copy, modify, and distribute this software
   and its documentation for any purpose, without fee, and
   without written agreement is hereby granted, provided that the
   above copyright notice and the following two paragraphs appear
   in all copies of this software.

   IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO
   ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR
   CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE
   AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA
   HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

   THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY
   WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
   WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
   PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS"
   BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO
   PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
   MODIFICATIONS.
*/

#include "threads/synch.h"
#include <stdio.h>
#include <string.h>
#include "threads/interrupt.h"
#include "threads/thread.h"
#include "debug.h"
/* Compare two threads by priority.  Used for sorting a list of
/* Initializes semaphore SEMA to VALUE.  A semaphore is a
   nonnegative integer along with two atomic operators for
   manipulating it:

   - down or "P": wait for the value to become positive, then
     decrement it.

   - up or "V": increment the value (and wake up one waiting
     thread, if any). */
void
sema_init (struct semaphore *sema, unsigned value) 
{
  ASSERT (sema != NULL);

  sema->value = value;
  list_init (&sema->waiters);
}

/* Down or "P" operation on a semaphore.  Waits for SEMA's value
   to become positive and then atomically decrements it.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but if it sleeps then the next scheduled
   thread will probably turn interrupts back on. */
void 
sema_down(struct semaphore *sema)
{
  enum intr_level old_level;

  ASSERT(sema != NULL);  // 断言 sema 不为 NULL，确保传递了一个有效的信号量
  ASSERT(!intr_context());  // 断言当前不在中断上下文，确保不在中断处理程序中调用 sema_down()

  old_level = intr_disable(); // 关中断
  while (sema->value == 0)  // 若信号量值为 0，则阻塞当前线程
  {
    list_insert_ordered(&sema->waiters, &thread_current()->elem, thread_cmp_priority, NULL); // 将当前线程按优先级有序插入等待队列
    thread_block();  // 阻塞当前线程
  }
  sema->value--; // 信号量值减 1，表示获取了资源
  intr_set_level(old_level); // 开中断
}

/* Down or "P" operation on a semaphore, but only if the
   semaphore is not already 0.  Returns true if the semaphore is
   decremented, false otherwise.

   This function may be called from an interrupt handler. */
bool
sema_try_down (struct semaphore *sema) 
{
  enum intr_level old_level;
  bool success;

  ASSERT (sema != NULL);

  old_level = intr_disable ();
  if (sema->value > 0) 
    {
      sema->value--;
      success = true; 
    }
  else
    success = false;
  intr_set_level (old_level);

  return success;
}

/* Up or "V" operation on a semaphore.  Increments SEMA's value
   and wakes up one thread of those waiting for SEMA, if any.

   This function may be called from an interrupt handler. */
void 
sema_up(struct semaphore *sema)
{
  enum intr_level old_level;

  ASSERT(sema != NULL);  // 断言 sema 不为 NULL，确保传递了一个有效的信号量

  old_level = intr_disable(); // 关中断
  if (!list_empty(&sema->waiters))  // 如果等待队列不为空
  {
    list_sort(&sema->waiters, thread_cmp_priority, NULL); // 将等待队列按优先级排序，确保最高优先级的线程在前面
    thread_unblock(list_entry(list_pop_front(&sema->waiters), struct thread, elem)); // 唤醒最高优先级的线程
  }

  sema->value++; // 信号量值加 1，表示释放了资源
  thread_yield(); // 让出 CPU，以便更高优先级的线程能够运行
  intr_set_level(old_level); // 开中断
}

static void sema_test_helper (void *sema_);

/* Self-test for semaphores that makes control "ping-pong"
   between a pair of threads.  Insert calls to printf() to see
   what's going on. */
void
sema_self_test (void) 
{
  struct semaphore sema[2];
  int i;

  printf ("Testing semaphores...");
  sema_init (&sema[0], 0);
  sema_init (&sema[1], 0);
  thread_create ("sema-test", PRI_DEFAULT, sema_test_helper, &sema);
  for (i = 0; i < 10; i++) 
    {
      sema_up (&sema[0]);
      sema_down (&sema[1]);
    }
  printf ("done.\n");
}

/* Thread function used by sema_self_test(). */
static void
sema_test_helper (void *sema_) 
{
  struct semaphore *sema = sema_;
  int i;

  for (i = 0; i < 10; i++) 
    {
      sema_down (&sema[0]);
      sema_up (&sema[1]);
    }
}

/* Initializes LOCK.  A lock can be held by at most a single
   thread at any given time.  Our locks are not "recursive", that
   is, it is an error for the thread currently holding a lock to
   try to acquire that lock.

   A lock is a specialization of a semaphore with an initial
   value of 1.  The difference between a lock and such a
   semaphore is twofold.  First, a semaphore can have a value
   greater than 1, but a lock can only be owned by a single
   thread at a time.  Second, a semaphore does not have an owner,
   meaning that one thread can "down" the semaphore and then
   another one "up" it, but with a lock the same thread must both
   acquire and release it.  When these restrictions prove
   onerous, it's a good sign that a semaphore should be used,
   instead of a lock. */
void
lock_init (struct lock *lock)
{
  ASSERT (lock != NULL);

  lock->holder = NULL;
  sema_init (&lock->semaphore, 1);
}

/* Acquires LOCK, sleeping until it becomes available if
   necessary.  The lock must not already be held by the current
   thread.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep.

   优先级捐赠：在等待锁之前，如果锁被持有，当前线程会将其优先级捐赠给持有线程，以防止优先级反转，并沿着等待链一直向上捐赠。
   信号量等待：通过 sema_down 操作进入休眠等待锁的释放。
   更新锁状态：在获取锁后，禁用中断以原子方式更新锁的持有者、清除等待状态，并恢复中断状态。
   */
void 
lock_acquire(struct lock *lock)
{
  struct thread *current_thread = thread_current(); // 当前正在执行的线程
  struct lock *l; // 遍历指针，用于遍历锁的捐赠链
  enum intr_level old_level;

  ASSERT(lock != NULL); // lock 指针不能是空指针，确保传递了一个有效的锁结构
  ASSERT(!intr_context()); // 不能在中断处理程序中调用该函数
  ASSERT(!lock_held_by_current_thread(lock)); // 锁不能被当前线程持有，防止死锁

  // 优先级捐赠
  if (lock->holder != NULL)  // 如果锁已经被其他线程持有
  {
    current_thread->lock_waiting = lock; // 设置当前线程正在等待的锁为 lock
    l = lock; // 将遍历指针 l 初始化为当前线程正在等待的锁 lock
    while (l && current_thread->priority > l->max_priority) // 遍历锁的捐赠链，找到优先级最高的线程
    {
      l->max_priority = current_thread->priority; // 更新锁的最大优先级为当前线程的优先级
      thread_donate_priority(l->holder); // 捐赠当前线程的优先级给锁的持有者
      l = l->holder->lock_waiting; // 继续遍历锁的捐赠链，找到优先级最高的线程
    }
  }
  sema_down(&lock->semaphore); // 获取锁对应的信号量，如果信号量值为 0 则阻塞当前线程

  // 当 sema_down 返回时，线程已成功获取锁，下面将更新锁的状态
  old_level = intr_disable(); // 关中断

  current_thread = thread_current(); // 重新获取当前线程的指针
  if (!thread_mlfqs)  // 如果未启用多级反馈队列调度
  {
    current_thread->lock_waiting = NULL; // 清除等待状态，当前线程不再等待任何锁
    lock->max_priority = current_thread->priority; // 重置锁的最大优先级，将锁的 max_priority 字段设置为当前线程的实际优先级
    thread_hold_the_lock(lock); // 将锁添加到当前线程持有的锁列表中
  }
  lock->holder = current_thread; // 将锁的持有者设置为当前线程

  intr_set_level(old_level);  // 开中断
}

/* Tries to acquires LOCK and returns true if successful or false
   on failure.  The lock must not already be held by the current
   thread.

   This function will not sleep, so it may be called within an
   interrupt handler. */
bool
lock_try_acquire (struct lock *lock)
{
  bool success;

  ASSERT (lock != NULL);
  ASSERT (!lock_held_by_current_thread (lock));

  success = sema_try_down (&lock->semaphore);
  if (success)
    lock->holder = thread_current ();
  return success;
}

/* Releases LOCK, which must be owned by the current thread.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to release a lock within an interrupt
   handler. */
void
lock_release (struct lock *lock) 
{
  ASSERT (lock != NULL);  // lock 指针不能是空指针，确保传递了一个有效的锁结构
  ASSERT (lock_held_by_current_thread (lock));  // 确保当前线程正在持有锁 lock

  if (!thread_mlfqs)  // 如果未启用多级反馈队列调度
    thread_remove_lock(lock);  // 从当前线程持有的锁列表中移除锁 lock

  lock->holder = NULL;  // 释放锁，将锁的持有者设置为 NULL
  sema_up (&lock->semaphore); // 释放锁对应的信号量，唤醒等待该锁的线程
}

/* Returns true if the current thread holds LOCK, false
   otherwise.  (Note that testing whether some other thread holds
   a lock would be racy.) */
bool
lock_held_by_current_thread (const struct lock *lock) 
{
  ASSERT (lock != NULL);

  return lock->holder == thread_current ();
}

/* One semaphore in a list. */
struct semaphore_elem 
  {
    struct list_elem elem;              /* List element. */
    struct semaphore semaphore;         /* This semaphore. */
  };

/* Initializes condition variable COND.  A condition variable
   allows one piece of code to signal a condition and cooperating
   code to receive the signal and act upon it. */
void
cond_init (struct condition *cond)
{
  ASSERT (cond != NULL);

  list_init (&cond->waiters);
}

/* Atomically releases LOCK and waits for COND to be signaled by
   some other piece of code.  After COND is signaled, LOCK is
   reacquired before returning.  LOCK must be held before calling
   this function.

   The monitor implemented by this function is "Mesa" style, not
   "Hoare" style, that is, sending and receiving a signal are not
   an atomic operation.  Thus, typically the caller must recheck
   the condition after the wait completes and, if necessary, wait
   again.

   A given condition variable is associated with only a single
   lock, but one lock may be associated with any number of
   condition variables.  That is, there is a one-to-many mapping
   from locks to condition variables.

   This function may sleep, so it must not be called within an
   interrupt handler.  This function may be called with
   interrupts disabled, but interrupts will be turned back on if
   we need to sleep. */
void
cond_wait (struct condition *cond, struct lock *lock) 
{
  struct semaphore_elem waiter;

  ASSERT (cond != NULL);
  ASSERT (lock != NULL);
  ASSERT (!intr_context ());
  ASSERT (lock_held_by_current_thread (lock));
  
  sema_init (&waiter.semaphore, 0);
  list_push_back (&cond->waiters, &waiter.elem);
  lock_release (lock);
  sema_down (&waiter.semaphore);
  lock_acquire (lock);
}

/* If any threads are waiting on COND (protected by LOCK), then
   this function signals one of them to wake up from its wait.
   LOCK must be held before calling this function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to signal a condition variable within an
   interrupt handler. */
void 
cond_signal(struct condition *cond, struct lock *lock UNUSED)
{
  ASSERT(cond != NULL);  // cond 指针不能是空指针，确保传递了一个有效的条件变量结构
  ASSERT(lock != NULL);  // lock 指针不能是空指针，确保传递了一个有效的锁结构
  ASSERT(!intr_context());  // 不能在中断处理程序中调用该函数
  ASSERT(lock_held_by_current_thread(lock)); // 确保当前线程正在持有锁 lock

  if (!list_empty(&cond->waiters))  // 如果等待队列不为空
  {
    list_sort(&cond->waiters, cond_sema_cmp_priority, NULL);  // 将等待队列按优先级排序，确保最高优先级的线程在前面
    sema_up(&list_entry(list_pop_front(&cond->waiters), struct semaphore_elem, elem)->semaphore); // 唤醒最高优先级的线程
  }
}

/* Wakes up all threads, if any, waiting on COND (protected by
   LOCK).  LOCK must be held before calling this function.

   An interrupt handler cannot acquire a lock, so it does not
   make sense to try to signal a condition variable within an
   interrupt handler. */
void
cond_broadcast (struct condition *cond, struct lock *lock) 
{
  ASSERT (cond != NULL);
  ASSERT (lock != NULL);

  while (!list_empty (&cond->waiters))
    cond_signal (cond, lock);
}

/* 按优先级排序条件变量等待队列中的线程 */
bool 
cond_sema_cmp_priority(const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
{
  struct semaphore_elem *sa = list_entry(a, struct semaphore_elem, elem);
  struct semaphore_elem *sb = list_entry(b, struct semaphore_elem, elem);
  return list_entry(list_front(&sa->semaphore.waiters), struct thread, elem)->priority > list_entry(list_front(&sb->semaphore.waiters), struct thread, elem)->priority;
}
